#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <functional>
#include <cmath>

template <
	class T,
	class COMPARE = std::less<T>
>
struct sparse_table
{
	typedef T value_type;
	typedef unsigned int size_type;
	typedef COMPARE comparer;
	typedef std::vector<value_type> vector_type;

	inline size_type log2(size_type len)
	{
		return std::log(len)/log(2);
		size_type tmp = 0;
		for (; size_type(1 << tmp) <= len; tmp++); // FIXME 11 neednot write size_type
		return tmp - 1;
	}

	sparse_table(vector_type const & data, comparer cmp = comparer())
		: data(data), cmp(cmp)
	{
		size_type n = data.size();
		size_type len = log2(n);
		st.resize(n);
		for (typename std::vector<vector_type>::iterator it = st.begin();
				it != st.end(); ++it)
			(*it).resize(len + 1);

		for (size_type i = 0; i < n; i++) st[i][0] = i;
		for (size_type l = 1; l <= len; l++)
			for (size_type i = 0; (i + (1<<l) - 1) < n; i++)
				if (cmp(data[ st[i][l - 1] ], data[ st[i + (1<<(l-1))][l - 1] ]))
					st[i][l] = st[i][l - 1];
				else
					st[i][l] = st[i + (1 << (l-1))][l - 1];
	}

	size_type query_interval_index(size_type l, size_type r) // [l, r]
	{
		int k = log2(r - l + 1);
		if (cmp(data[ st[l][k] ], data[ st[r - (1<<k) + 1][k] ]))
			return st[l][k];
		else
			return st[r - (1<<k) + 1][k];
	}

	value_type query_interval(size_type l, size_type r) // [l, r]
	{
		return data[ query_interval_index(l, r) ];
	}

private:
	std::vector<vector_type> st; // store the index of the dest value
	vector_type const & data;
	comparer cmp;
};


int const maxl = 200007;
int const maxn = 100007;
int const dis = 100000;
int count[maxl];
int da[maxn], left[maxn], right[maxn];
int n, q;

int main()
{
	while (std::scanf("%d", &n) != EOF && n) {
		std::scanf("%d", &q);
		std::vector<int> num(n);
		std::fill(count, count + maxl, 0);
		for (int i = 0; i < n; i++) {
			std::scanf("%d", &da[i]);
			count[da[i] + dis]++;
		}
		right[n-1] = n-1;
		for (int i = n-2; i >= 0; i--)
			if (da[i] == da[i + 1]) right[i] = right[i+1];
			else					right[i] = i;
		left[0] = 0;
		for (int i = 1; i < n; i++)
			if (da[i] == da[i - 1]) left[i] = left[i-1];
			else					left[i] = i;

		for (int i = 0; i < n; i++) num[i] = count[da[i] + dis];
		sparse_table<int, std::greater<int> > st(num);

		for (int i = 0, l, r; i < q; i++) {
			std::scanf("%d%d", &l, &r);
			l--; r--;
			int tl = right[l] + 1, tr = left[r] - 1;
			if (tl > r + 1) tl = r + 1;
			if (tr < l - 1) tr = l - 1;
			int max = std::max(r - tr, tl - l);
			/*
			std::cerr << tl << ' ' << tr << '\n';
			std::cerr << "max: " << max << '\n';
			*/
			if (tl <= tr)
				max = std::max(max, st.query_interval(tl, tr));
			std::printf("%d\n", max);
		}
	}
}

